%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%
% Time
%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\subsection{\label{subsec:time-in-databases}Time in Databases}
The concept of time has been studied in the database framework for a long time. A true standard for adding temporal aspects to relational databases does not exist, but there is a consensus in the literature \cite{Dyreson1994} on what is called a \emph{temporal database}: a temporal database is a database dealing with some aspects of time in its schema.
In a temporal DBMS, a \textbf{chronon} is the shortest duration of time supported by the system. In temporal databases, some temporal attributes can be managed without treating the attribute differently from non-temporal attributes. The time described by such an attribute is called \textbf{user defined time} (\emph{UDT}). In addition to UDT, the following types of time can be discerned in a temporal database, all of which are handled exceptionally by the DBMS:

\begin{itemize}
	\item
	\textbf{Transaction time} (\emph{TT}) \cite{Rowe1987,Jensen1991} denotes the time when the fact (object) is stored in the database. It is usually append-only: as the past cannot be changed, TT cannot be changed either. Furthermore, at the moment of insertion, a TT can be neither in the past nor in the future.
	\item
	\textbf{Valid time} (\emph{VT}) \cite{Jensen1994,Sarda1990,McKenzie1981} denotes the time when the fact (object) is true in the modelled reality. A fuzzy extension has been proposed by \cite{Garrido2009}. 
%	\item
%	User defined time: It is an uninterpreted attribute. The domain is date/time. The query language has no special support for it.
	\item
	\textbf{Decision time} (\emph{DT}) \cite{Nascimento1995,Chakravarthy1994,Etzion1992,Ozsoyoglu1995} denotes the time when an event was decided to happen. 
	\end{itemize}
	 
	For example, consider a database containing employee contract descriptions. The time when the employee's contract is valid, represented by an interval, is the VT. The time when the employee's contract is stored in the database is the TT. The time when the decision for hiring this employee was made is a DT.

% is a non-decomposable unit of time.  it  There are two ways to represent a chronon: as a point or as an interval \cite{655777}.

When working with these time concepts, the Data Manipulation Language (\emph{DML}, which is part of the standard database querying language SQL) is extended to deal with possible temporal inconsistencies within the data and to handle more complex (temporal) queries. 
%Next to these concepts, also \textbf{user defined time} (\emph{UDT}) is discerned. UDT is an uninterpreted attribute in the date/time domain. This means that the attribute uses the date/time domain, but the database model does not treat the attribute differently from non-temporal attributes.
Depending on the time managed, a database is classified as either a \textbf{Valid Time Database} (\emph{VTDB}), a \textbf{Transaction Time Database} (\emph{TTDB}), a \textbf{bi-temporal database} (both valid and transaction time are managed) or a \textbf{tri-temporal} or \emph{multitemporal} database (valid time, transaction time and decision time are managed).

%\subsection{Temporal Elements}
%%	
%	In order to define a temporal database model, some basic elements should be defined \cite{Dyreson:1994:CGT:181550.181560}:
%	\begin{itemize}
%	\item A	\textbf{chronon} is a non-decomposable unit of time. In a temporal DBMS, it is the shortest duration of time supported by the system. There are two ways to represent a chronon: as a point or as an interval \cite{655777}.
%	\item
%	\emph{Event}: An instant of time. Usually, an event is said to be occur during time $t$ if it occurs during the chronon represented by $t$.
%	\item
%	\emph{Interval}: The time between two events. The representation is very often a set of contiguous chronons.
	%\item
	%\emph{Span}: A directed duration of time. A duration is an amount of time with known  lenght but no specific starting or ending chronons. The span can be either positive, denoting a forward motion of time or negative, denoting a backward motion of time.
%	\item A	\textbf{timestamp} is a time value associated with some object in the database.	
	
%	\item The	\textbf{lifespan} (of a database object)is the time over which it is defined. The lifespan of a valid time object denotes the time when the corresponding object exists. The lifespan of a transaction time object is the value of the timestamp.
	
	
	
	
	
%	Depending on the type of time the meaning is different:
%		\begin{itemize}
%		\item
%		Lifespan of a valid time object: Refers the time when the corresponding object exists.	
%		\item
%		Lifespan of a transaction time object: The transaction time of a database object refers when the object is stored in the database. The lifespan is the value of the timestamp.		
%		\end{itemize}
%	\end{itemize}
	
%	In the temporal database thesaurus, \emph{'Snapshot'} is the word for non-temporal matters. As a temporal database is a generalization for relational databases, an \emph{snapshot database} is a relational database. Furthermore, a \emph{snapshot relation} is a relation incorporating neither valid nor transaction time.

%\subsection{Main issues when dealing with time}
%Among others, the following problems are present when dealing with time in a database:

%	\begin{itemize}	
%	\item \textbf{Granularity} denotes a partition on the set of chronons. The conversion between several granularities is studied in \cite{Lin97efficientconversion}. Granularity is the base of the temporal model in \cite{Cru97}. An object-oriented implementation is in \cite{624013}.
%	\item	To ensure \textbf{consistency}, temporal databases usually redefine the primary key of a relation. The new primary key takes into account the presence of the time. In order to keep the consistency, the DML is re-defined. For example, in a VTDB, the temporal update sentence is usually composed by an update sentence (closing the old row) plus an insert sentence (creating the new row).
%	\end{itemize}
%Guy's suggestion: instead of imprecision, use imperfection which is more general.
\subsubsection{Imperfection and time}
The representation of imprecision and its semantics when dealing with time has been studied for a long time. Several proposals for representing and handling imprecise time indications can be found in \cite{DeCaluwe1997,DeTre1997}. Also, the changes between several granularities can be seen as a source of imprecision \cite{Devos1998}.

In this paper we will consider two kinds of imperfection:
\begin{itemize}
\item \textbf{Imperfection in the database}; the knowledge about the temporal data contains some imperfection. E.g., a database record shows that \emph{`The car was in the garage around April.'}
 \item \textbf{Imprecision in the query specification}; it denotes the imprecision in the specification of temporal criteria by the user, when querying. E.g., \emph{`The user wants a car which was in the garage around April.'}
\end{itemize}

\subsubsection{Representation}
Several proposals for managing uncertain time in a database exist. Some proposals work with rough sets \cite{Qiang2009}, and some others rely on possibility distributions for representing uncertainty in time \cite{Dyreson1998,Garrido2009,Galindo2001}. To compare temporal possibility distributions, the extensions of the classical Allen's operators \cite{Allen1983} are defined in \cite{Ohlbach2004,Nagypal2003,Dubois2003a,Schockaert2008}.
%In the proposal section, we will follow the representation by means of possibility distributions, in order to work with both satisfaction and dissatisfaction degrees. Also, in order to work properly with fuzzy operators, the underlying domain should be numeric. 
% Take a look into this:
%In this paper, the representation for the dates will follow the Julian Day Number (JDN) representation \cite{Dir96}.

%If the starting points and/or the end points of the interval representing the time are not known precisely, it is easy to fuzzify them, using, e.g., two triangular possibility distributions.


In order to deal with uncertainty in time intervals, several proposals have been made. Here, two approaches are described: the first one, based on \emph{Fuzzy Validity Periods}~\cite{Garrido2009} and the second one, based on \emph{Possibilistic Valid-time Periods}~\cite{JoseEnriquePons2012}.

\begin{definition}
A \textbf{Fuzzy Validity Period}\cite{Garrido2009} (\emph{FVP}) is defined as a fuzzy time interval specifying when the data regarding an object are valid. A fuzzy time interval is then the fuzzification of a crisp time interval.\\
\end{definition}


Several options to transform possibility distributions corresponding to the fuzzy starting point and the fuzzy end point into a consistent FVP exist \cite{Garrido2009}, e.g (Fig. \ref{fig:fuzzy-validity-period}):
\begin{itemize}
\item The \textbf{convex hull} approach is the most intuitive approach. The resulting FVP is the convex hull of the union of both possibility distributions.
\item The \textbf{uncertainty preserving} approach. The amount of uncertainty is maintained at the edges of the possibility distribution representing the FVP \cite{Garrido2009}.
\end{itemize}

%%%%%%
% FUZZY VALIDITY PERIOD
%%%%%%
\begin{samepage}
\vspace*{13pt}
\begin{center}
{
\includegraphics[scale=0.25]{./graphs/comparisoncv.pdf}

}
\end{center}
%\centerline{ \psfig{file=./graphs/Y-time-point.eps}}
\vspace*{10pt}
\end{samepage}

\fcaption{\label{fig:fuzzy-validity-period}Transformation to obtain the FVP. The top graph shows the two triangular possibility distributions. The middle graph shows the convex hull validity period, the bottom one shows the result of the second transformation, which maintains the imprecision.}
%  \label{fig:fuzzy-validity-period}
\vspace*{13pt}


The main feature for the FVP is the optimization for the storage. The compact representation is the result of a conjunctive semantic. The object is valid within all the time points inside the starting and ending points.


\begin{definition}
A \textbf{Possibilistic Valid-time Period} (\emph{PVP}) is an ill-known interval of time specifying when the data regarding an object are valid.
\end{definition}

Note that the PVP represents only one crisp time interval, but for some reason, it is (partially) unknown.

The main advantage for the PVP is that it preserves all the information for both starting and ending points\cite{Pons2011,Pons2012}. Table \ref{tbl:comparative-pvp-fvp} is a comparative between PVP and FVP. The following list defines the items in the comparative:

\begin{enumerate}
\item Domain: The domain of the possibility distribution modelled by the approach.
\item Implementation of relationships: How to implement a relationship.
\item Allen's relations: Are the Allen's relations defined?
\item Storage: The way the data are stored in the database.
\item Possibility measures: Does the framework provide a possibility measure for any relation between the temporal elements?
\item Necessity measures:  Does the framework provide a necessity measure for any relation between the temporal elements?
\end{enumerate}


%%
%% comparison table between pvp and fvp.
%%
\begin{samepage}
\vglue13pt
%\begin{table}[htbp]
\tcap{Comparative PVP vs FVP}
%\centerline{\small DATA TYPES}
\vglue-6pt
\centerline{\small\baselineskip=13pt
\begin{tabular}{c p{2cm} p{2cm}}\\
Item & PVP & FVP\\
\hline
(1) & $\Pow(\R)$ & $\R$ \\
(2) & Ill-known constraints. & Ad-hoc operators. \\
(3) & $\checkmark$ & - \\
(4) & Two distributions one for each endpoint. & Only one distribution. \\ 
(5) & $\checkmark$ & $\checkmark$ \\
(6) & $\checkmark$ & - \\
\hline\\
\end{tabular}
\label{tbl:comparative-pvp-fvp}
} 
\end{samepage}
In the rest of the paper we will work only with PVP to represent valid-time intervals.


\subsection{\label{subsubsec:Understanding-valid-time-databases}Understanding Valid-time Databases}
This subsection is devoted to describe the behaviour of a crisp valid-time database. For the sake of simplicity, only the three main operations in the Data Manipulation Language (CReate Update, Delete) are shown. Usually the DML operations in a temporal database are re-defined (a typical update sentence in SQL could be expressed by means of a couple of insert and update sentences). Therefore, for the sake of clarity, these high level primitives in the DML for a valid-time database are usually noted as Insert, Modify and Delete. In the following subsections each primitive is defined and explained. Finally, an illustrative example is given. For a more complete information on the behaviour of a bitemporal database, please refer to ~\cite{Jensen1994}.

\begin{definition}
\label{def:valid-time-relation}
\emph{Valid-time relation.}
Consider the following definitions and notations:

\begin{itemize}
 \item A set of non-temporal attributes.
	\begin{equation}
	\label{eq:attribute-set}
	A = \left \lbrace A_1, A_2, \ldots, A_n \right \rbrace
	\end{equation}
      The domain for each attribute $A_1, \ldots, A_n$ is $D_1, \ldots, D_n$ respectively. 
\item The original primary key $A_K$ is a subset of the attributes in $A$.
      \begin{equation}
       \label{eq:primary-key-a}
      A_K \subseteq A
      \end{equation}
\item Two attributes, $S$  and $E$ for the starting and ending points respectively. $I$ defines the valid time interval for the data. 
\begin{equation}
 \label{eq:attribute-time-interval}
I = \left \lbrace S, E \right \rbrace
\end{equation}

$\T$ is the time domain.

\item Then $R$, the schema for the valid-time relation is:
\begin{equation}
 \label{eq:valid-time-relation}
R = A \cup  I
\end{equation}
\item The primary key for the valid-time relation $R$ is:
\begin{equation}
 \label{eq:valid-time-temporal-pk}
PK = A_K \cup I
\end{equation}


\item We will note by $r$ any valid instance of $R$. 
      \begin{equation}
       \label{eq:valid-time-instance}
      r \subseteq D_1\ x\ \ldots\ x\ D_n x\ T x\ T
      \end{equation}


     % \end{itemize}
\item $V(t)$ is the set of all the versions for a given tuple $t$. Formally,

\begin{equation}
 \label{eq:all-the-versions}
V(t) =\left \lbrace t_i \in r, t_i\left[A_K\right] = t\left[A_K\right] \right \rbrace
\end{equation}
Obviously, $t$ itself is included in the set.
% If a tuple $t$ contains more than one version, the result of $Vt$ is a set. We will use the index $k$ to address the elements of the set. E.g. $Vt = \left \lbrace t_1, t_2, \ldots, t_n \right \rbrace$. Then $t_k , k \in \left \lbrace 1, \ldots, n \right \rbrace$ is an element of $Vt$.
\end{itemize}
\end{definition}
We will illustrate the definitions with an example.

\begin{example}
Consider the set of attributes $A = \left \lbrace A_1, A_2, A_3 \right \rbrace$. The primary key for these attributes is given by $A_K = \left \lbrace A_1, A_2 \right \rbrace$. Let $I = \left \lbrace S, E \right \rbrace$ be the set of temporal attributes that define the validity period of the data. $R$ is the valid-time relation and $r$ is an instance of the relation. The instance $r$ is given by the following elements. $r = \left \lbrace \left(a_{11}, a_{12}, a_{13}, s_1 ,e_1 \right) \right.$,  $\left(a_{21}, a_{22}, a_{23}, s_2, e_2 \right)$ , $\left. \left(a_{11}, a_{12}, a_{31}, s_3, e_3 \right) \right \rbrace$. The instance $r$ is illustrated in Table \ref{tbl:sample-definitions}. 
Consider the tuple $t_1 = \left(a_{11}, a_{12}, a_{13}, s_1 ,e_1 \right)$. Then,
\begin{align}
 \nonumber
 t_1\left[S \right]&=s_1\\
 \nonumber
t_1[E]&=e_1\\
 \nonumber
t_1[S,E]&= \left(s_1, e_1\right)\\
 \nonumber
t_1\left[A_K\right] &= \left(a_{11}, a_{12} \right) \\
 \nonumber
t_1\left[PK\right] &=\left(a_{11}, a_{12}, s_1, e_1\right)\\
 \nonumber
V(t_1) &= \left \lbrace t_1, t_3 \right \rbrace
\end{align}



\end{example}

\begin{samepage}
\vglue13pt
%\begin{table}[htbp]
\tcap{\label{tbl:sample-definitions}Sample database containing the instance $r$ of the valid-time relation $R$.}
%\centerline{\small DATA TYPES}
\vglue-6pt
\centerline{\small\baselineskip=13pt
\begin{tabular}{c c c c c c}\\
\hline
& \textbf{A$_1$}  & \textbf{A$_2$}  & $A_3$ & $S$ & $E$ \\
\hline
$t_1$&$a_{11}$ & $a_{12}$ & $a_{13}$ & $s_1$ & $e_1$ \\
$t_2$ & $a_{21}$ & $a_{22}$ & $a_{23}$ &  $s_2$ & $e_2$ \\
$t_3$ & $a_{11}$ & $a_{12}$ & $a_{31}$ & $s_3$ & $e_3$\\
\hline\\
\end{tabular}
}
\end{samepage}




% Consider $\A$ be the set of all the entities, and let $A=\left(A_1, \ldots, A_n \right), A \in \A$ be the set of attributes that define an entity. Let $I = \left(S_i, E_i \right)$ be the set of attributes defining the time interval. The set $\I$ is the set of all the time intervals. The pair $\left(A, I\right)$ expresses that the data regarding the entity A are valid during the crisp time interval I. Let $R \subseteq \A \  x\  \I$ be a valid-time relation. Then, the following equation indicates that the pair $\left(A, I\right)$ is in the relation R:
% 
% \begin{equation}
% \label{eq:rel-def}
% \left( R, \left(A , I\right) \right)
% \end{equation}
% 
% 
In order to simplify the algorithms for the manipulation of data, some auxiliary functions and constants are defined:


\begin{definition}
 \label{def:from-beginning}
\emph{From the beginning (FB).} 
Consider the elements in definition \ref{def:valid-time-relation} and a tuple t. We will say $t[S]=FB$ when $t[S]=- \infty$. 
% $i = \left(s, e \right)$ be the value for a time interval as given equation \eqref{}.
% $A=\left(A_1, \ldots, A_n \right)$ be the set of attributes that define an entity and $I = \left(S_i, E_i \right), S_i, E_i \in \T$ the set of attributes defining the time interval. Let $R \subseteq \A\  x\  \I$ be a valid-time relation. We will say $I = \left(FB, E_i \right)$ when $I = \left(- \infty, E_i \right)$.
%The from the beginning constant is used when the value for $s_i$ is equal to $-\infty$.
\end{definition}

\begin{definition}
 \label{def:until-changed}
\emph{Until changed (UC).} 
Consider the elements in definition \ref{def:valid-time-relation} and a tuple t. We will say $t[E]=UC$ when $t[E]=+ \infty$. 
% Consider $A=\left(A_1, \ldots, A_n \right)$ be the set of attributes that define an entity. Let $\T$ be the time domain, and $I = \left(S_i, E_i \right), S_i, E_i \in \T$ the set of attributes defining the time interval. Let $R \subseteq \A\  x\  \I$ be a valid-time relation. We will say  $I = \left(S_i, UC \right)$ when $I = \left(S_i, +\infty \right)$.
%The until changed constant is used when the value for $e_i$ is equal to $+\infty$.
\end{definition}

\begin{definition}
\emph{Current.} 
Consider the elements in definition \ref{def:valid-time-relation}. We will say that the tuple $t$ is current in the instance $r$ of the relation $R$ when $t[E]=UC$.
\end{definition}


%If the pair $\left(A, I \right)$ with $I = \left(S_i, UC \right), S_i \in \T$ is in the relation $R$, then, it is said that the pair $\left(A, I \right)$ is \emph{current} in the relation.

For example, let us consider the last row in Table \ref{tbl:library-sample}. The value for the time interval is $I = \left(4/4/2012 , UC \right)$. The meaning is that the document with ID = 3 was valid the  4/4/2012 and it is still valid. The document with ID = 3 is current in the relation.


\begin{example}
\label{ex:library-database}
 Consider a historical database containing diplomatic documents. The starting and the ending dates say when the diplomatic document is valid. It is possible that a diplomatic document is valid for a period of time and several years later it becomes valid again. The following elements are stored: an identifier of the document (ID), the entity that issues the document and the dates when the document is valid. Table \ref{tbl:library-sample} illustrates the first version of the database, after three insertions. In this example, $A = ($ ID, Entity $)$ and $I = ($ Start, End $)$.
\end{example}

\begin{samepage}
\vglue13pt
%\begin{table}[htbp]
\tcap{\label{tbl:library-sample}Sample historical database}
%\centerline{\small DATA TYPES}
\vglue-6pt
\centerline{\small\baselineskip=13pt
\begin{tabular}{c c c c}\\
\hline
\textbf{ID}  & Entity  & Start & End \\
\hline
3 & E.U. & 15/3/2012 & 30/3/2012 \\
4 & N.A.T.O.  & 25/3/2012 & 4/4/2012 \\
5 & C.E.I. & 18/3/2012 & 2/4/2012\\
3 & E.U. & 4/4/2012 & UC \\
\hline\\
\end{tabular}
}
\end{samepage}


\begin{definition}
\label{def:current-in-relation}
\emph{Current $\left(r,a_k \right)$.}
Consider the elements in definition \ref{def:valid-time-relation}. The function Current $\left(r,a_k \right)$ returns the crisp time interval of a tuple $t$ with primary key $a_k$ as follows:
% 
% Consider $A=\left(A_1, \ldots, A_n \right), A \in \A$ be the set of attributes that define an entity and $I = \left(S_i, UC \right)$ the set of attribute defining the time interval. Let $R \subseteq \A\  x\  \I$ be a valid-time relation. The function Current $\left(R, A \right)$ returns the crisp time interval $I$ if the entity $A$ is currently in the relation $R$ or the empty set, if the entity $A$ is not currently in the relation. It is defined as follows:

%Consider an object $A$ and a relation $R$ in a temporal database. The function Current$\left(R, A \right)$ obtains the tuple $\left(A, I \right)$ that is current in the relation $R$, that is it, $I = \left[a, +\infty \right]$.

\begin{align}
\label{eq:current-in-relation}
\mbox{Current} \left(r, a_k\right) &=& \\ 
\begin{cases}
\nonumber
t[S,E] & \mbox{ if } \exists t \in r : t[E]=UC \mbox{ and }\\
& t[A_K]=a_k \\
\emptyset & \mbox{ otherwise}
\end{cases}
\end{align}
\end{definition}

For example, the function Current(r, 3) returns the time interval $\left(4/4/2012 , UC  \right)$. Conversely, Current(r, (4,`N.A.T.O.')) returns the empty set.


The Allen's relations between two time intervals are shown in Figure \ref{fig:allen-rel}. The complete implementation of the relations using only the starting and the ending points is defined in~\cite{Nagypal2003}.

\begin{samepage}
\vspace*{13pt}
\begin{center}
{
\includegraphics[scale=0.5]{./graphs/allen.pdf}

}
\end{center}
%\centerline{ \psfig{file=./graphs/Y-time-point.eps}}
\vspace*{10pt}
\fcaption{\label{fig:allen-rel}Allen's relations for two crisp time intervals $I$ and $J$. Note that the crisp time interval $I$ is fixed and the different positions of the interval $J$ illustrate the Allen's relations.}
\vspace*{13pt}
\end{samepage}

We will use two of the Allen's relations: Overlaps and During which will be defined as follows.

\begin{definition}
\emph{Overlaps:}
 \label{def:overlaps}
Given two time intervals defined by the couples of values $i_1 = \left(s_1, e_1 \right)$ and $i_2 = \left(s_2, e_2\right)$, it is said that $i_1$ overlaps $i_2$ if:
\begin{align}
 \label{eqn:overlaps}
i_1 \text{ overlaps } i_2  = \left((\left(s_1 < s_2  \right) \wedge \left(e_1 < e_2  \right)\right)\\
\nonumber
\vee \left((\left(s_1 > s_2  \right) \wedge \left(e_1 > e_2  \right)\right)
\end{align}


\end{definition}
  

\begin{definition}
\emph{During:}
 \label{def:during}
Given two time intervals defined by the couples of values $i_1 = \left(s_1, e_1 \right)$ and $i_2 = \left(s_2, e_2\right)$, it is said that $i_1$ during $i_2$ if:
\begin{align}
 \label{eqn:during}
i_1\text{ during } i_2  =& \left(s_1 > s_2  \right) \wedge \left(e_1 < e_2 \right)
\end{align}
\end{definition}

In the rest of the paper, and without losing generality, we will consider that the time granularity are days. Also, the dates will be given in the format \emph{dd/mm/yyyy}.


\begin{definition}
\emph{CloseR$\left(i_1, i_2\right)$:}
\label{def:close-a-crisp-interval-r}
Consider two crisp intervals defined by the couples of values $i_1 = \left(s_1, e_1 \right)$ and $i_2 = \left(s_2, e_2\right)$. The CloseR$\left(i_1, i_2 \right)$ function allows to close the right-open interval $i_1$ with respect to the first value $s_2$ in $i_2$:
\begin{align}
\label{eq:close-a-crisp-interval}
\mbox{CloseR} \left( i_1, i_2\right) &=& \\ 
\begin{cases}
\nonumber
%I & \mbox{ if } b \neq +\infty \\
%I=\left[a, c \right[ & \mbox{ if } b = +\infty \wedge J > I
\left(s_1,s_2-1\right) & \mbox{ if } e_1 = UC \mbox{ and } i_2 \mbox{ During } i_1 \\
i_1 & \mbox{ otherwise}
\end{cases}
\end{align}
\end{definition}

For example, consider two time intervals, $i_1 = \left(4/4/2012, UC \right)$ and $i_2 = \left(24/4/2012, UC \right)$. The result of applying the CloseR$\left(i_1, i_2 \right)$ is $i_1 = \left(4/4/2012, 23/4/2012 \right)$.




%Analogously, it is defined the function to close a left-open interval: 
%\begin{definition}
%\label{def:close-a-crisp-interval-l}
%CloseL$\left(I, J\right)$ 
%\begin{align}
%\mbox{CloseL} \left( I, J \right) &=& \\ 
%\begin{cases}
%\nonumber
%I & \mbox{ if } a \neq -\infty \\
%I=\left]d, b \right] & \mbox{ if } a = -\infty \wedge J < I
%\end{cases}
%\end{align}
%\end{definition}




%\begin{definition}
%\label{def:first-in-relation}
%Analogously, the function First$\left(R, A \right)$ obtains the tuple $\left(A, I \right)$ where $I$ is a right-open interval and which is the first version in the relation $R$, that is it, $I = \left[-\infty, b \right]$.
%\begin{align}
%\label{eq:first-in-relation}
%\mbox{First} \left(R, A \right) &=& \\ 
%\begin{cases}
%\nonumber
%I & \mbox{ if } \exists b \in I : (A,I) \in R \wedge a = -\infty \\
%\emptyset & \mbox{ in any other case }
%\end{cases}
%\end{align}
%
%\end{definition}



Now it is possible to close the current version of an entity by using \eqref{eq:close-a-crisp-interval} and \eqref{eq:current-in-relation}. This functionality is required to add or update new information about an existing entity in the relation.

\begin{definition}
\label{def:close-current-version}
\emph{Close-current$\left(r, t\right)$}.
Consider the elements in definition \ref{def:valid-time-relation}. The function Close-current$\left(r, t \right)$ closes any current version $t_k$ of the entity given by $t$ and adds the new version $t$. For the implementation $t_{CUR}$ and $t_{UP}$ variables are defined:
\begin{align}
 \label{eq:variables-current-version}
t_{CUR}\left[A_k\right] &= t[A_K]\\\nonumber
t_{CUR}\left[S,E \right] &= \mbox{Current } \left(r, t[A_K] \right)\\\nonumber
t_{UP}[A_k] &= t[A_k]\\
 t_{UP}\left[S,E \right] &= \mbox{CloseR }\left(t_{CUR}\left[S,E \right], t[S,E] \right)\nonumber
\end{align}
Then, $t_{CUR}$ is the current version of the entity given by the tuple $t$, and $t_{UP}$ is the updated version of the tuple $t_{CUR}$. In this updated version, the time interval given by $i_{UP}$ is closed with respect to the tuple $t$.


\begin{eqnarray}
\label{eq:close-current}
\text{Close-current} \left(r, t \right) =\\
\begin{cases}
\nonumber
r - t_{CUR} \cup \lbrace t_{UP}\rbrace \cup \lbrace t \rbrace
& \mbox{ if } \mbox{Current } \left(r, t[A_K] \right) \neq \emptyset \\
% R - \left(A, I \right) \cup \left \lbrace \left(A, \mbox{ CloseR } \left(I, J\right) \right)\right \rbrace \cup \left \lbrace\left(A, J\right) \right \rbrace  \\
% \nonumber
% \mbox{ if  Current } \left(R, A \right) \neq \emptyset\\ %\wedge J > \mbox{ CloseR } \left(I, J \right)   \\
r , \text{ otherwise}
\end{cases}
\end{eqnarray}
\end{definition}

For example, consider the document with ID = 3 in Table \ref{tbl:library-sample}. The current version of the document started on 4/4/2012. The document was not valid anymore but, for some reason, the date  was not registered. The document was valid again on 24/4/2012. Then, the Close-current function closes the current version of the document and adds a new version. First, the function CloseR is applied with $i_1 = \left(4/4/2012, UC \right)$ and $i_2 = \left(24/4/2012, UC \right)$. Hence, the value for the time interval $i_1$ is $ \left(4/4/2012, 23/4/2012 \right)$. Then, the modifications on the value for the time interval $i_1$ are stored. Finally a new row with the current values of the document and the time interval $i_2$ is stored.
% patient with ID = 3 in Table \ref{tbl:library-sample}. The current version arrived on 4/4/2012. The patient left the hospital but, for some reason, the date  was not registered. The patient arrived again at the hospital on 24/4/2012. Then, the Close-current function allows to close the current version of the patient and insert a new version. First, the function CloseR is applied with $I = \left(4/4/2012, UC \right)$ and $J = \left(24/4/2012, UC \right)$. Hence, the value for the time interval $I$ is $ \left(4/4/2012, 23/4/2012 \right)$. Then, the modifications on the value for the time interval $I$ are stored. Finally, a new row with the current values of the patient and the time interval $J$ is stored.
The result of this operation is illustrated on Table \ref{tbl:library-sample-2}.




%It is also possible to append at the beggining by using \eqref{def:close-a-crisp-interval-l} and \eqref{def:first-in-relation}.
%\begin{definition}
%\label{def:append-first-version}
%Consider an object $A$, the relation $R$ and a time interval $J$. Then, the function append-first$\left(R,A,J \right)$ closes any right open version of the object $A$ if it exists and add the new version $\left(A, J \right)$.
%
%\begin{eqnarray}
%%\label{eq:close-current}
%\text{Append-first} \left(R, A, J \right) =\\
%\begin{cases}
%\nonumber
%\big \lbrace R - \left(A, I \right) \cup \left \lbrace \left(A, \mbox{ CloseL } \left(I, J\right) \right) \cup \left(A, J\right)\right \rbrace  \big \rbrace \\
%\nonumber
%\mbox{ if } I = \mbox{ First } \left(R, A \right) \wedge J < \mbox{ CloseL } \left(I, J \right)   \\
%\nonumber R , \text{ in any other case}
%\end{cases}
%\end{eqnarray}
%\end{definition}
\subsubsection{\label{subsubsec:modify}Modify}
This operation adds new information about an existing entity (given by the tuple $t$) in the instance $r$ of the relation $R$. The modify operation does not remove any previous value of the entity. It closes the current version and adds a new version.


%Note that the modify operation is only applicable when the object $A$ is current in the relation $R$; $ \left(A, I \right) \in R, I = \left[a, +\infty \right]$.

\begin{definition}
 \emph{Modify(r, t)}.
Consider the elements in definition \ref{def:valid-time-relation}. The algorithm for the modify operation is defined as follows.
\end{definition}


\begin{align}
\label{eq:modify}
\MOD \left( r, t\right) =\\
%\begin{cases}
\nonumber
\mbox{ Close-current }\left(r, t\right) %\\
% \mbox{ if Current}\left(R ,A \right) \neq \emptyset \\
% R,  \mbox{ otherwise }
%\end{cases}
\end{align}


\subsubsection{\label{subsubsec:insert}Insert}
The user wants to store an entity (given by the tuple $t$) which is valid in the instance $r$ of the relation $R$ during the time interval specified by $i = \left(s, e \right)$.
%
%
%The interpretation of the insert operation is the following: The user wants to store in the database that an object $A$  is true for some period(s) of time $I$ in the given relation $R$. To indicate that the object $A$ is current in the relation, the special value Until Current, $\UC$  is used. 
There are two main cases when performing a create operation:
\begin{enumerate}
\item The entity was never in the relation: The entity is added with the valid-time indicated by the crisp interval $i$. 
% In the example, this correspond with the following insertion sentences:
% \begin{verbatim}
% Insert(3,'Dracula',
% (15/3/2012, 30/3/2012));
% Insert(4,'Frankenstein',
% (25/3/2012, 4/4/2012));
% Insert(5,'Harry Potter',
% (18/3/2012, 2/4/2012));
% \end{verbatim}


\item The entity is in the relation. Depending on the value of the time interval, there are three possibilities:
	\begin{enumerate}
	\item Insert $t$ in the instance $r$ of the relation $R$. If the time interval $i$ does not overlap any other valid-time interval in the instance $r$ relation $R$ for the entity. For example, consider that the document with ID = 3 began again to be valid on 4/4/2012 and it is still currently valid. This is illustrated in Table \ref{tbl:library-sample}.
%  The insert sentence is:
% 	      \begin{verbatim}
% Insert(3,'Dracula',
% (4/4/2012, UC));
% 	      \end{verbatim}


	\item Modify and close the current version of $t$ and insert the new version. For example, consider now that the document with ID = 3 was valid on 24/4/2012. Here the problem is that the document with ID = 3 was valid on 4/4/2012 but, for some reason, the ending date was not stored. If the document is again valid, then it is necessary to set the ending date and add a new row with the new starting date. This is illustrated in Table \ref{tbl:library-sample-2}.
%  the insert sentence is:
% 	    \begin{verbatim}
% Insert(3,'Dracula',
% (24/4/2012, UC));
% 	      \end{verbatim}
	\item Reject the insertion, if the time interval $i$ does overlap any existing valid-time interval for the entity $t$ in the instance $r$ of the relation $R$. For example, consider that the document manager wants to introduce a past valid-time for the document with ID = 3. The validity period for the document is $[$6/4/2012, 25/4/2012$]$. As the dates do overlap, it is not possible that the document was valid at that time interval. Therefore, the insertion is rejected.
%  The insert sentence is:
% 
% 	      \begin{verbatim}
% Insert(3,'Dracula',
% (6/4/12/2012,25/4/2012));
% 	    \end{verbatim}


	\end{enumerate}

\end{enumerate}
\begin{samepage}
\vglue13pt
%\begin{table}[htbp]
\tcap{\label{tbl:library-sample-2}Sample historical database}
%\centerline{\small DATA TYPES}
\vglue-6pt
\centerline{\small\baselineskip=13pt
\begin{tabular}{c c c c}\\
\hline
\textbf{ID}  & Entity  & Start & End \\
\hline
3 & E.U. & 15/3/2012 & 30/3/2012 \\
4 & N.A.T.O. & 25/3/2012 & 4/4/2012 \\
5 & C.E.I.  & 18/3/2012 & 2/4/2012\\
3 & E.U. & 4/4/2012 & 23/4/2012 \\
3 & E.U. & 24/4/2012 & UC \\
\hline\\
\end{tabular}
}
\end{samepage}

\begin{definition}
 \emph{Insert(r, t)}.
Consider the elements in definition \ref{def:valid-time-relation}. Then, the algorithm for the implementation of the insert operation is defined as follows.
\end{definition}



\begin{align}
\label{eq:insert}
\INS \left(r, t\right) =\\
\begin{cases}
\nonumber
r & \mbox{ if }  \exists t_k \in V(t), \left(t[S,E] \mbox{ overlaps } t_k[S,E]\right)\\
\nonumber
r \cup \lbrace t \rbrace
& \mbox{ if }  V(t)=\emptyset \mbox{ or }\\
\nonumber & \forall t_k \in V(t), \lnot \left(t[S,E] \mbox{ overlaps } t_k[S,E]\right)\\
% 
% R \cup \left(A, I \right) & \mbox{ if }  (A, I ) \not \in R  \mbox{ or } \\
%  &   \left(A, J\right) \in R \mbox{ and } \lnot \left(I \mbox{ Overlaps } J\right) \\
\mbox{modify(r, t)} & \mbox{ otherwise }    %\mbox{ if } \exists J \left(A,J\right) \in R \wedge \mbox{Current(A,J)} \\ 
%R, &   
\end{cases} 	
\end{align}

\subsubsection{\label{subsubsec:del}Delete}
The delete operation logically removes a current entity $t$ which is valid in the instance $r$ of the relation $R$.
\begin{definition}
 \emph{Delete(r, t)}.
Consider the elements in definition \ref{def:valid-time-relation}.The algorithm for the delete operation is defined as follows.
% 
% Let $R \subseteq \A\  x\  \I$ be a valid-time relation and  $A=\left(A_1, \ldots, A_n \right), A \in \A$ be the set of attributes that define an entity and $I = \left(S_i,E_i\right)$ the set of attributes defining the time interval. The algorithm for the delete operation is defined as follows.
\end{definition}


\begin{align}
\label{eq:delete}
\DEL \left(r, t\right) =
%\begin{cases}
\nonumber
r - V(t)
% 
% 
% R - \left \lbrace \left(A, I_1 \right),  \ldots, \left(A, I_n \right)   \right \rbrace, & \forall I_i : \left( A, I_i \right) \in R\\
% R, & \mbox{ otherwise }  
%\end{cases} 	
\end{align}
The set $V(t)$ is computed as explained in definition \ref{def:valid-time-relation} and contains all the versions for the tuple $t$.


For example, consider that the document manager wants to delete the history for the document with ID = 3. The result of this operation is shown in Table \ref{tbl:library-sample-3}. 

% The delete sentence is:
% 
% \begin{verbatim}
%  Delete(3,'Dracula');
% \end{verbatim}

\begin{samepage}
\vglue13pt
%\begin{table}[htbp]
\tcap{\label{tbl:library-sample-3}Sample historical database}
%\centerline{\small DATA TYPES}
\vglue-6pt
\centerline{\small\baselineskip=13pt
\begin{tabular}{c c c c}\\
\hline
\textbf{ID}  & Entity  & Start & End\\
\hline
4 & N.A.T.O. & 25/3/2012 & 4/4/2012 \\
5 & C.E.I. & 18/3/2012 & 2/4/2012\\
\hline\\
\end{tabular}
}
\end{samepage}

% \subsubsection{\label{subsubsec:revise}Revise}
% This operation replaces the old values for the entity $A'= \left(a_1', \ldots, a_n' \right) $ with the new values specified by $A = \left(a_1, \ldots, a_n \right)$ in the relation $R$, at a given time interval $I$. This operation is used when a correction on the values for the entity $A$ should be done.
% \begin{align}
% \REV\left(R, \left(A, I \right) \right)=\\
% \begin{cases}
% \nonumber
%  R - \left(A', I \right) \cup \left \lbrace \left(A, I \right) \right \rbrace & \mbox{ if } \left(A', I \right) \in R  \\
%    %: A = \left(a_1, \ldots, a_n \right),\\
% %A'= \left(a_1', \ldots, a_n' \right)   \\   
% R & \mbox{ otherwise }
% \end{cases}
% \end{align} 
% 
% For example, consider now that the librarian wants to make a correction in the title for the book with ID = 5. The new title is `Harry Potter IV'. The result of this operation is illustrated in Table \ref{tbl:library-sample-3}.
%  Then, the revise sentence is:
% 
% \begin{verbatim}
% Revise(5,'Harry Potter IV', 
% (18/3/2012, 2/4/2012));
% \end{verbatim}

